﻿#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<math.h>
#include"let.h"
using namespace std;
class node {
public:
	node() {
	}
	node(point _prev, point _local) {
		prev  = _prev;
		local = _local;
	}
	node(point _prev, point _local,int _G,int _H) {
		prev = _prev;
		local = _local;
		G = _G;
		H = _H;
		F = G + H;
	}
	point prev;
	point local;
	int G;
	int H;
	int F;
	
};
class Solution {
public:
	vector<node> openlist;
	vector<node> closelist;
	string strs[100];
	int next[8][2] = { {0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{-1,1},{1,-1} };
					  //右0   左1     下2   上3   右下4  左上5   右上6   左下7
	Solution() {
		freopen("C:\\users\\l\\desktop\\input.txt", "r", stdin);
		for (int i = 0; i < 100; i++) {
			cin >> strs[i];
		}
	}
	void showmap(){
		for (int i = 0; i < 100; i++) {
			for (int j = 0; j < 100; j++) {
				cout << strs[i][j];
			}
			cout << endl;
		}
	}
	void astar(int sx,int sy,int ex,int ey) {
		openlist.push_back(node(point(-1, -1), point(sx, sy),0,0));
		while (!openlist.empty()) {
			int x;
			int y;
			int F = 99999;

			//在openlist里面找F最小的，用xy保存，xy为当前值
			for (auto t : openlist) {
				if (F > t.F) {
					F = t.F;
					x = t.local.x;
					y = t.local.y;
				}
			}
			strs[x][y] = '2';
			cout << x << " " << y << endl;
			
			//在openlist里面把上面找的F最小的节点删除，并把其加入closelist
			vector<node>::iterator it = openlist.begin();
			while (it != openlist.end()) {
				if ((*it).local.x ==x && (*it).local.y == y) {
					closelist.push_back((*it));
					it = openlist.erase(it);
				}
				else {
					it++;
				}
			}

			//找(x,y)四面的点，加入openlist

			//这里开关
			for (int i = 0; i < 8; i++) {
				int nextx = x + next[i][0];
				int nexty = y + next[i][1];
				if (!(nextx < 100 && nextx >= 0)) {
					continue;
				}
				if (!(nexty < 100 && nexty >= 0)) {
					continue;
				}
				if (strs[nextx][nexty] != '0'){
					continue;
				}
				//是否在closelist中
				int isExistClose = 0;
				for (auto t : closelist) {
					if (t.local.x == nextx && t.local.y == nexty) {
						isExistClose = 1;
					}
				}
				if (isExistClose == 1) {
					continue;
				}


				//判断四面的某一个点是否在openlist里面
				int isExistOpen = 0;//开始假设不存在
				for (auto &t : openlist) {
					//如果存在
					if (nextx == t.local.x&&nexty == t.local.y) {
						isExistOpen = 1;
						//计算新的G
						int newG = calcG(point(x, y), point(nextx, nexty));
						//重新计算F
						if (newG < t.G) {
							t.G = newG;
							t.F = t.G + t.H;
						}
						
						t.prev.x = x;
						t.prev.y = y;
						/*
							这里不能斜着走
							不计算，不加入openlist
						*/
					}
				}
				//如果openlist不存在这个元素
				if (isExistOpen == 0) {
					node temp(point(x, y), point(nextx, nexty));
					temp.G = calcG(point(x, y), point(nextx, nexty));
					temp.H = manhattanDist(temp.local, point(ex,ey));
					temp.F = temp.G + temp.H;
					openlist.push_back(temp);

					//找到大肥猪啦！！！！！
					if (temp.local.x == ex && temp.local.y == ey) {
						cout << ex << " " << ey << endl;
						strs[x][y] = '2';
						return ;
					}
				}
				continue;
			}

			continue;
		}
		return ;
	}

};
int main() {
	
	Solution s;
	s.astar(36,20,37,85);
	s.showmap();
}